class Solution {
public:
    int ans;   
    int _k;           
    int _n;                                    
    bool dfs(vector<int>& nums,vector<int>& vis,int cur,int sum,int cnt){
        if(cnt == _k) return true;
        if(sum == ans) return dfs(nums,vis,_n-1,0,cnt+1);
        
        for(int i = cur;i >= 0;i--){
            if(vis[i] || sum + nums[i] > ans) continue;
            vis[i] = 1;
            if(dfs(nums,vis,i-1,sum+nums[i],cnt)){
                return true;
            }
            vis[i] = 0;
            if(sum == 0) return false;
        }
        
        return false;
    }   
                                        
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;
        for(int& x : nums){
            sum += x;
        }
        if(sum % k != 0) return false;
        ans = sum / k;
          _n = n;
          _k = k;
        
        vector<int> vis(n);
        sort(nums.begin(),nums.end());
                                                    
        return dfs(nums,vis,n-1,0,0);
    }
};  
